function maxSubArray(nums: number[]): number {
  // const dp: number[] = [];

  // dp[0] = nums[0];

  // const n = nums.length;

  // for (let i = 1; i < n; i++) {
  //   dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
  // }

  // return Math.max(...dp);

  const n = nums.length;
  let preValue = nums[0];
  let max = preValue;

  for (let i = 1; i < n; i++) {
    preValue = Math.max(nums[i], nums[i] + preValue);
    max = Math.max(preValue, max);
  }
  return max;
}

// const nums = [-2, 1, -3, 4, -1, 2, 1, -5, -4];
const nums = [5, 4, -1, 7, 8];
const res = maxSubArray(nums);
console.log(res);
